"""
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
"""

from typing import List
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        result = []
        if n == 0:
            return []
        self.kuohao(n,n,'',result)
        return result

    """
    l:剩余的左括号数量
    r:剩余的右括号数量
    item:生成的括号
    result:最后返回的结果
    """
    def kuohao(self,l,r,item,result):
        if l > r:
            return
        if l == 0 and r == 0:
            result.append(item)
        if l > 0:
            self.kuohao(l-1,r,item + '(',result)
        if r > 0:
            self.kuohao(l,r-1,item + ')',result)